package tree;

public class MinPriorityQueue<T extends Comparable<T>> {
    private T[] data;
    private int size;
    public MinPriorityQueue(int capacity){
        data = (T[]) new Comparable[10];
    }
    public int size(){
        return this.size;
    }
    public boolean isEmpty(){
        return this.size==0;
    }
    public void insert(T t){
        data[++this.size] = t;
        swim(this.size);
    }
    public T delMin(){
        T t = data[1];
        exchange(1,size);
//        data[this.size--] = null;
        this.size--;
        sink(1);
        return t;
    }
    private void sink(int k){
        int min;
        while (k*2<=this.size){
            if (k*2+1<=this.size){
                min = better(k*2,k*2+1)?k*2+1:k*2;
            }else {
                min = k*2;
            }
            if (!better(k,min)){
                break;
            }
            exchange(k,min);
            k=min;
        }
    }
    private boolean better(int i,int j){
        return data[i].compareTo(data[j])>0;
    }
    public void swim(int k){
        while (k>1){
            if (better(k/2,k)){
                exchange(k,k/2);
            }
            k/=2;
        }
    }
    public void  exchange(int i,int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
}
